package 二叉树相关问题.层次遍历;

import java.util.Deque;
import java.util.LinkedList;

public class 二叉树的最大宽度 {
    public int widthOfBinaryTree(TreeNode root) {
        if (root == null)
            return 0;
        //deque 支持两端插入和取出
        Deque<TreeNode> q = new LinkedList();
        root.val = 0;
        q.offer(root);
        int ans = 0;
        while (!q.isEmpty()) {
            ans = Math.max(ans, q.getLast().val - q.getFirst().val + 1);
            for (int i = q.size(); i > 0; i--) {
                TreeNode poll = q.poll();
                if (poll.left != null) {
                    q.offer(poll.left);
                    poll.left.val = 2 * poll.val + 1;
                }
                if (poll.right != null) {
                    q.offer(poll.right);
                    poll.right.val = 2 * poll.val + 2;
                }
            }
        }
        return ans;
    }
}
